INT_MAX = 10 ** 6

# 与计算所有字母之间的距离
DISTANCE_TABLE = [[INT_MAX] * 26 for _ in range(26)]
for ii in range(26):
    for jj in range(ii, 26):
        x1, y1 = divmod(ii, 6)
        x2, y2 = divmod(jj, 6)
        DISTANCE_TABLE[ii][jj] = DISTANCE_TABLE[jj][ii] = abs(x1 - x2) + abs(y1 - y2)


class Solution:
    def minimumDistance(self, word: str) -> int:
        # 定义状态矩阵：dp[w][i][j] 在输入完w后，左手位置在i，右手位置在j的情况下的最小移动距离（w省略）
        # i=26时左手还没有按键，j=26时右手还没有按键
        dp1 = [[INT_MAX] * 27 for _ in range(27)]
        dp1[26][26] = 0

        for ch in word:
            k = ord(ch) - 65
            dp2 = [[INT_MAX] * 27 for _ in range(27)]

            for i in range(27):
                for j in range(27):
                    if dp1[i][j] < INT_MAX:
                        # 移动左手
                        if i < 26:
                            dp2[k][j] = min(dp2[k][j], dp1[i][j] + DISTANCE_TABLE[i][k])
                            # print((i, j), "->", (k, j), "=", dp2[k][j])

                        # 移动右手
                        if j < 26:
                            dp2[i][k] = min(dp2[i][k], dp1[i][j] + DISTANCE_TABLE[j][k])
                            # print((i, j), "->", (i, k), "=", dp2[i][k])

            # 第1次使用左手
            for j in range(27):
                if dp1[26][j] < INT_MAX:
                    dp2[k][j] = min(dp2[k][j], dp1[26][j])
                    # print((26, j), "->", (k, j), "=", dp2[k][j])

            # 第1次使用右手
            for i in range(27):
                if dp1[i][26] < INT_MAX:
                    dp2[i][k] = min(dp2[i][k], dp1[i][26])
                    # print((i, 26), "->", (i, k), "=", dp2[i][k])

            dp1 = dp2

        ans = INT_MAX
        for i in range(27):
            for j in range(27):
                ans = min(ans, dp1[i][j])
        return ans


if __name__ == "__main__":
    print(Solution().minimumDistance("CAKE"))  # 3
    print(Solution().minimumDistance("HAPPY"))  # 6
    print(Solution().minimumDistance("NEW"))  # 3
    print(Solution().minimumDistance("YEAR"))  # 7
